﻿#include <map>
#include <iostream>

using namespace std;

template <class key, class value>
class map_iterator_wraper {
public:
    value*& operator * () { return current->second; }
    bool operator == (const map_iterator_wraper& other) const { return current == other.current; }
    bool operator == (const typename map<key, value*>::iterator& other) const { return other == current; }
    bool operator != (const map_iterator_wraper& other) const { return !operator == (other); }
    bool operator != (const typename map<key, value*>::iterator& other) const { return other != current; }
    map_iterator_wraper& operator ++ () { current++; return *this; }
    value* operator -> () { return current -> second; }
    map_iterator_wraper (const typename map<key, value*>::iterator& src) : current(src) {}
    map_iterator_wraper operator = (const typename map<key, value*>::iterator& src) { current = src; return *this; }
private:
    typename map<key, value*>::iterator current; // Итератор по отображению
};

template <class Name>
class BiGraph {
public:
    class Edge;
    class Vertex;
    typedef map_iterator_wraper<Name, Vertex> vertex_iterator;
    typedef map_iterator_wraper<Vertex*, Edge> edge_iterator;
    typedef pair<vertex_iterator, vertex_iterator> vertices_range;
    typedef pair<edge_iterator, edge_iterator> edges_range;

    BiGraph() : m_edges_count(0) {}
    
    class Vertex {
    public:
        friend class BiGraph;
        Vertex (const Name& n) : m_name (n) {}
        const Name& get_name () const { return m_name; }
        edges_range in_edges () {
            return make_pair(m_in_edges.begin(), m_in_edges.end());
        }
        edges_range out_edges () {
            return make_pair(m_out_edges.begin(), m_out_edges.end());
        }
    private:
        Name m_name;
        map<Vertex*, Edge*> m_out_edges; // Ребра выходящие из данной вершины.
        map<Vertex*, Edge*> m_in_edges; // Ребра входящие в данную вершину.
    };
    
    class Edge {
    public:
        Edge (Vertex* start, Vertex* end, double weight) : m_start_vertex (start), m_end_vertex (end), m_weight (weight) {}
        Vertex* get_start () { return m_start_vertex; }
        Vertex* get_end () { return m_end_vertex; }
    private:
        Vertex* m_start_vertex; // Начальная вершина.
        Vertex* m_end_vertex; //Конечная вершина.
        double m_weight; // Вес ребра.
    };

    // Добавление вершины: вернет false, если вершина с таким именем уже существует.
    bool add_vertex (const Name& v) {
        if (m_vertices.find (v) != m_vertices.end ()) { return false; }
        else {
            m_vertices.insert ( make_pair ( v, new Vertex(v) ) );
            return true;
        }
    }

    // Добавление ребра. Петли запрещены
    Edge* add_edge (const Name& start, const Name& end, double weight) {
        if (start == end) { return NULL; }
        Vertex* start_vertex = find_or_create_vertex (start);
        Vertex* end_vertex = find_or_create_vertex (end);
        typename map<Vertex*, Edge*>::iterator existing_edge = start_vertex->m_out_edges.find (end_vertex);
        if (existing_edge == start_vertex->m_out_edges.end ()) {
            ++m_edges_count;
            Edge* new_edge = new Edge(start_vertex, end_vertex, weight);
            start_vertex->m_out_edges.insert (std::make_pair (end_vertex, new_edge));
            end_vertex->m_in_edges.insert (std::make_pair (start_vertex, new_edge));
            return new_edge;
        } else { return existing_edge->second; }
    }

    // Удаление ребра: вернет false, если такого ребра нет
    bool delete_edge (const Name& start, const Name& end) {
        if (m_vertices.find (start) == m_vertices.end ()) {
            return false; // Нет вершины.
        }
        if (m_vertices.find (end) == m_vertices.end ()) {
            return false; // Нет вершины.
        }
        Vertex* start_vertex = m_vertices[start];
        Vertex* end_vertex = m_vertices[end];
        if (start_vertex->m_out_edges.find (end_vertex) == start_vertex->m_out_edges.end ()) {
            return false; // Нет ребра
        }
        start_vertex->m_out_edges.erase (end_vertex);
        delete end_vertex->m_in_edges[start_vertex];
        end_vertex->m_in_edges.erase (start_vertex);
        return true;
    }

    // Возвращает количество вершин графа
    size_t vertices_count () const { return m_vertices.size(); }

    // Возвращает количество ребер графа
    size_t edges_count () const { return m_edges_count; }

    // Очистка графа
    void clear ()  {
        for (vertex_iterator ptr_v = m_vertices.begin(); ptr_v != m_vertices.end (); ++ptr_v) {
            for (edge_iterator ptr_e = ptr_v->m_in_edges.begin(); ptr_e != ptr_v->m_in_edges.end(); ++ptr_e) {
                delete *(ptr_e);
            }
            ptr_v->m_out_edges.clear();
            ptr_v->m_in_edges.clear ();
            delete *ptr_v;
        }
        m_vertices.clear();
        m_edges_count = 0;
    }

    // Получение списка вершин
    vertices_range vertices () { return make_pair( vertex_iterator(m_vertices.begin()), vertex_iterator(m_vertices.end()) ); }

    //Деструктор
    ~BiGraph () { clear(); }

private:
    map<Name, Vertex*> m_vertices; // Вершины в графе
    size_t m_edges_count;
    Vertex* find_or_create_vertex (const Name& v) {
        if (m_vertices.find (v) == m_vertices.end ()) {
            Vertex* new_vertex = new Vertex (v);
            m_vertices.insert (std::make_pair(v, new_vertex));
            return new_vertex;
        }
        return m_vertices[v];
    }
};

int main() {
    BiGraph<int> BG;
    BG.add_edge(1,6,8);
    BG.add_edge(2,1,10);
    BG.add_edge(2,3,15);
    BG.add_edge(3,1,-5);
    BG.add_edge(3,5,18);
    BG.add_edge(5,1,0);
    BG.add_edge(5,6,13);
    BG.add_edge(6,3,-9);
    BG.add_edge(6,4,-6);
    BG.add_edge(6,6,-6); //Петля
    BG.add_vertex(7);
    BG.add_vertex(100);
    BG.add_vertex(999);
    
    cout<<"Edges: "<<BG.edges_count();
    cout<<endl;
    cout<<"Vertices: "<<BG.vertices_count();
    cout<<endl;

    BG.clear ();

    system("pause");

    return 0;
}